package leetcode.d_1_99;

import java.util.LinkedList;
import java.util.List;

// https://leetcode.cn/problems/spiral-matrix/
// 旋转矩阵
public class P54 {
    public static void main(String[] args) {
        P54 test = new P54();
        System.out.println(test.spiralOrder(new int[][]{{1,2,3}, {4,5,6}, {7,8,9}})); // [1,2,3,6,9,8,7,4,5]
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        List<Integer> res = new LinkedList<>();
        // 定义4个边界
        int top = 0;
        int bottom = m-1;
        int left = 0;
        int right = n-1;

        while(true) {
            // 从左到右
            for (int i=left; i<=right; i++) {
                res.add(matrix[top][i]);
            }
            if (++top > bottom) {
                break;
            }
            // 从上到下
            for (int i=top; i<=bottom; i++) {
                res.add(matrix[i][right]);
            }
            if (--right < left) {
                break;
            }
            // 从右到左
            for (int i=right; i>=left; i--) {
                res.add(matrix[bottom][i]);
            }
            if (--bottom < top) {
                break;
            }
            // 从下到上
            for (int i=bottom; i>=top; i--) {
                res.add(matrix[i][left]);
            }
            if (++left > right) {
                break;
            }
        }
        return res;
    }
}
